public class SwapTwoPairsOfNodes {
    /*
    * ___________________需要时常复习
    * 两两交换链表中的节点
    * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
    * 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
    * */

    public static void main(String[] args) {

    }

    public ListNode mySolution(ListNode head){
        if(head == null)
            return null;
        if(head.next == null)
            return head;
        ListNode result = head.next;
        // 虚拟头节点，便于每两个节点之间的拼接
        ListNode dummyHead = new ListNode(-1,null);
        ListNode nextNode = head.next;
        ListNode flag;
        while (nextNode != null){
            // 交换节点
            flag = nextNode.next;
            head.next = nextNode.next;
            nextNode.next = head;
            // 和已经换好的链连接上
            dummyHead.next = nextNode;
            // 成为新的链尾
            dummyHead = head;
            // 无后续节点，结束循环
            if(flag == null)
                break;
            head = flag;
            nextNode = flag.next;
        }
        return result;
    }
}
